`
https://leetcode.cn/problems/find-median-from-data-stream/
`

var MedianFinder = function () {
  this.minpq = new MinHeap()
  this.maxpq = new MaxHeap()
};

/** 
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function (num) {
  // 新增数小于等于最大堆堆顶，放入最大堆
  if (this.maxpq.size() === 0 || num <= this.maxpq.peek()) {
    this.maxpq.push(num)
    // 只允许最大堆比最小堆多一个元素
    if (this.maxpq.size() - this.minpq.size() > 1) {
      const value = this.maxpq.pop()
      this.minpq.push(value)
    }
  } else {
    this.minpq.push(num)
    // 最小堆大小不得大于最大堆
    if (this.minpq.size() > this.maxpq.size()) {
      const value = this.minpq.pop()
      this.maxpq.push(value)
    }
  }
};

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function () {
  if (this.maxpq.size() === this.minpq.size()) {
    return (this.maxpq.peek() + this.minpq.peek()) / 2
  } else {
    return this.maxpq.peek()
  }
};

class Heap {
  constructor(compare) {
    this.heap = [];
    this.compare = compare;
  }
  size() {
    return this.heap.length;
  }
  isEmpty() {
    return this.heap.length === 0;
  }
  peek() {
    return this.heap[0] ?? undefined;
  }
  push(value) {
    this.heap.push(value);
    this.bubbleUp(this.heap.length - 1);
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
        [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
        index = parentIndex;
      } else break;
    }
  }
  pop() {
    if (this.isEmpty()) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (!this.isEmpty()) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return top;
  }
  sinkDown(index) {
    let current = index;
    const length = this.size();
    while (true) {
      const left = 2 * current + 1;
      const right = 2 * current + 2;
      let target = current;
      if (left < length && this.compare(this.heap[left], this.heap[target]) < 0)
        target = left;
      if (right < length && this.compare(this.heap[right], this.heap[target]) < 0)
        target = right;
      if (target !== current) {
        [this.heap[current], this.heap[target]] = [this.heap[target], this.heap[current]];
        current = target;
      } else break;
    }
  }
  update(oldValue, newValue) {
    const index = this.heap.indexOf(oldValue);
    if (index === -1) return false;
    this.heap[index] = newValue;
    this.bubbleUp(index);
    this.sinkDown(index);
    return true;
  }
  remove(value) {
    const index = this.heap.indexOf(value);
    if (index === -1) return false;
    const last = this.heap.pop();
    if (index === this.heap.length) return true;
    this.heap[index] = last;
    this.bubbleUp(index);
    this.sinkDown(index);
    return true;
  }
  contains(value) {
    return this.heap.includes(value);
  }
}
class MaxHeap extends Heap {
  constructor() {
    super((a, b) => b - a);
  }
}
class MinHeap extends Heap {
  constructor() {
    super((a, b) => a - b);
  }
}

/** 
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */